﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol199
{
    public IList<int> RightSideView2(TreeNode root)//先来个DFS，递归法
    {//使用接口，只要继承这个接口的都可以返回

       
        
        List<int> result = new List<int>();
      
        int depth = 0;
        DFS(root,result, depth );
        return result;
    }

    private void DFS(TreeNode root, List<int> result,int depth)
    {
        if (root == null) return ;
        //判断一下是否把这个根加入结果
       

        if (depth == result.Count)//只有第一次到达这个深度，而且没有加入，就把这个最右边的加入
        {
            result.Add(root.val);
        }
            DFS(root.right, result,depth + 1);//先递归右边
        DFS(root.left, result, depth + 1);//右子树没有，就会暴露下一层的左边


    }


    public IList<int> RightSideView(TreeNode root)//先来个BFS，迭代
    {



        List<int> result = new List<int>();

      List<TreeNode> queue= new List<TreeNode>();
        if (root == null)
        {
            return result;
        }
        else
        {
            queue.Add(root);
        }
        
        while (queue.Count > 0)
        {
           
            int size= queue.Count;
           
            for (int i = 0; i < size; i++)//这里不可以使用queue.Count，这个实时计算会变化的
            {
                //root = queue[i];//这个数组一直在减少
                root = queue[0];
                //Console.WriteLine("index:"+i+"val"+root.val);
                queue.Remove(root);
                //queue.RemoveAt(0);
                if (i== size - 1)
                {
                    result.Add(root.val);
                }
                if (root.left != null)
                {
                    queue.Add(root.left);
                }
                if(root.right != null)
                {
                    queue.Add(root.right);
                }
              
            }

        }

        
        return result;
    }
}
class Program199
{

    static void Main199(string[] args)
    {
        string s = "1 2 5 3 4";
        string[] chars = s.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 2, 5, 1, 3, 4 };

        Solution105 solution105 = new Solution105();



        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);
        Sol199 sol= new Sol199();
        IList<int> res= sol.RightSideView(root);

        for(int i = 0;i < res.Count;i++)
        {
            Console.WriteLine(res[i]);
        }

    }
}
